#define DEBUG
#include <cstdio>

using namespace std;

const long long mods=1004535809, G=3;
const int maxsize=262144;

long long omg[maxsize], inv[maxsize], fact[maxsize], unfact[maxsize];

long long power(long long a, long long n) {
  if (n==0) {
    return 1;
  }
  long long s=1;
  for (; n>1; n/=2) {
    if (n%2) {
      s = s*a%mods;
    }
    a = a*a%mods;
  }
  return a*s%mods;
}

long long un(long long a) {
  return power(a, mods-2);
}

void ntt(long long *a, long long n, long long *omg) {
  long long temp;
  int log=0;
  for (; 1<<log<n; log++);
  for (int i=0, t=0; i<n; i++) {
    t = 0;
    for (int j=0; j<log; j++) {
      t |= ((i>>j)&1)<<(log-j-1);
    }
    if (i<t) {
      temp=a[i], a[i]=a[t], a[t]=temp;
    }
  }

  for (int len=2, m=1; len<=n; m=len, len*=2) {
    for (int i=0; i<n; i+=len) {
      for (int j=0; j<m; j++) {
	temp=omg[maxsize/len*j]*a[i+m+j]%mods;
	a[i+m+j] = (a[i+j]-temp+mods)%mods;
	a[i+j] = (a[i+j]+temp)%mods;
      }
    }
  }
}

void calc(long long *f, long long *g, int l, int r) {
  if (l==r-1) {
    if (l>1) {
      f[l] = (power(2, (long long)l*(l-1)/2)*unfact[l-1]%mods-f[l]+mods)%mods;
    }
  } else {
    static long long temp[3][maxsize];
    int mid=(l+r)/2;
    calc(f, g, l, mid);

    for (int i=0; i<mid-l; i++) {
      temp[0][i]=f[l+i];
    }
    for (int i=mid-l; i<2*r-2*l; i++) {
      temp[0][i]=0;
    }
    for (int i=0; i<r-l; i++) {
      temp[1][i]=g[i];
    }
    for (int i=r-l; i<2*r-2*l; i++) {
      temp[1][i]=0;
    }
    ntt(temp[0], 2*r-2*l, omg);
    ntt(temp[1], 2*r-2*l, omg);
    for (int i=0; i<2*r-2*l; i++) {
      temp[2][i] = temp[0][i]*temp[1][i]%mods;
    }
    ntt(temp[2], 2*r-2*l, inv);
    long long x=un(2*r-2*l);
    for (int i=0; i<2*r-2*l; i++) {
      temp[2][i] = temp[2][i]*x%mods;
    }

    for (int i=0; i<r-mid; i++) {
      f[mid+i] = (f[mid+i]+temp[2][i+mid-l])%mods;
    }

    calc(f, g, mid, r);
  }
}

int main() {
#ifdef DEBUG
  freopen("3303.in", "r", stdin);
  freopen("3303.out", "w", stdout);
#endif

  int n;
  scanf("%d", &n);

  static long long f[maxsize], g[maxsize];
  fact[0]=fact[1]=1;
  omg[0]=inv[0]=1;
  omg[1]=power(G, (mods-1)/maxsize), inv[1]=un(omg[1]);
  for (int i=2; i<maxsize; i++) {
    omg[i] = omg[i-1]*omg[1]%mods;
    inv[i] = inv[i-1]*inv[1]%mods;
    fact[i] = fact[i-1]*i%mods;
  }
  unfact[maxsize-1] = un(fact[maxsize-1]);
  for (int i=maxsize-1; i>1; i--) {
    unfact[i-1] = unfact[i]*i%mods;
  }

  f[0]=g[0]=0;
  for (long long i=1; i<=n; i++) {
    g[i] = power(2, i*(i-1)/2)*unfact[i]%mods;
  }
  f[1]=1;

  calc(f, g, 0, maxsize/2);

  f[n] = f[n]*fact[n-1]%mods;
  printf("%lld", f[n]);

  fclose(stdin);
  fclose(stdout);
  return 0;
}
